Learning Causal Models of Relational Domains.%2
Methods for discovering causal knowledge from observational data have been a persistent topic of AI research for several decades. Essentially all of this work focuses on knowledge representations for propositional domains. In this paper, we present several key algorithmic and theoretical innovations that extend causal discovery to relational domains. We provide strong evidence that effective learning of causal models is enhanced by relational representations. We present an algorithm, relational PC, that learns causal dependencies in a state-of-the-art relational representation, and we identify the key representational and algorithmic innovations that make the algorithm possible. Finally, we prove the algorithm’s theoretical correctness and demonstrate its effectiveness on synthetic and real data sets. 1
Resisting structural re%2Didentification in anonymized social networks.
We identify privacy risks associated with releasing network data sets and provide an algorithm that mitigates those risks. A network consists of entities connected by links representing relations such as friendship, communication, or shared activity. Maintaining privacy when publishing networked data is uniquely challenging because an individual’s network context can be used to identify them even if other identifying information is removed. In this paper, we quantify the privacy risks associated with three classes of attacks on the privacy of individuals in networks, based on the knowledge used by the adversary. We show that the risks of these attacks vary greatly based on network structure and size. We propose a novel approach to anonymizing network data that models aggregate network structure and then allows samples to be drawn from that model. The approach guarantees anonymity for network entities while preserving the ability to estimate a wide variety of network measures with relatively little bias. 1.
Accurate Estimation of the Degree Distribution of Private Networks.
Abstract—We describe an efficient algorithm for releasing a provably private estimate of the degree distribution of a network. The algorithm satisfies a rigorous property of differential privacy, and is also extremely efficient, running on networks of 100 million nodes in a few seconds. Theoretical analysis shows that the error scales linearly with the number of unique degrees, whereas the error of conventional techniques scales linearly with the number of nodes. We complement the theoretical analysis with a thorough empirical analysis on real and synthetic graphs, showing that the algorithm’s variance and bias is low, that the error diminishes as the size of the input graph increases, and that common analyses like fitting a power-law can be carried out very accurately. Keywords-privacy; social networks; privacy-preserving data mining; differential privacy. I.
Knowledge Discovery by Design.

Why Stacked Models Perform Effective Collective Classification.
Collective classification techniques jointly infer all class labels of a relational data set, using the inferences about one class label to influence inferences about related class labels. Typical collective classification schemes use computationally-intensive iterative algorithms or approximate joint inference techniques. Kou and Cohen recently introduced an efficient relational model based on stacking that, despite its simplicity, performs equivalently to more sophisticated joint inference approaches. This stacked relational model trains on the inferred labels of related instances, instead of the true labels which are not typically present at inference time. This permits the use of efficient exact inference in place of more computationally-intensive approximate joint inference. There are at least two possible causes for the unexpected high performance of the stacked approach: a reduction in inference bias (resulting from training on inferred rather than true labels) or a reduction in inference variance (due to the use of exact rather than approximate inference). Using experiments on both real and synthetic data, we show that the primary cause for the performance of the stacked model is the reduction in bias from learning the stacked model on inferred labels rather than the true labels. The reduction in variance due to conditional inference also contributes to the effect but it is not as strong. In addition, we show that the performance of the joint inference and stacked learners can be attributed to an implicit weighting of local and relational features at learning time. 1
Social networks looking ahead.

Resisting structural re%2Didentification in anonymized social networks.
We identify privacy risks associated with releasing network data sets and provide an algorithm that mitigates those risks. A network consists of entities connected by links representing relations such as friendship, communication, or shared activity. Maintaining privacy when publishing networked data is uniquely challenging because an individual’s network context can be used to identify them even if other identifying information is removed. In this paper, we quantify the privacy risks associated with three classes of attacks on the privacy of individuals in networks, based on the knowledge used by the adversary. We show that the risks of these attacks vary greatly based on network structure and size. We propose a novel approach to anonymizing network data that models aggregate network structure and then allows samples to be drawn from that model. The approach guarantees anonymity for network entities while preserving the ability to estimate a wide variety of network measures with relatively little bias. 1.
Optimistic pruning for multiple instance learning.

Exploiting Network Structure for Active Inference in Collective Classification.

Graph clustering with network structure indices.
Graph clustering has become ubiquitous in the study of relational data sets. We examine two simple algorithms: a new graphical adaptation of the k-medoids algorithm and the Girvan-Newman method based on edge betweenness centrality. We show that they can be effective at discovering the latent groups or communities that are defined by the link structure of a graph. However, both approaches rely on prohibitively expensive computations, given the size of modern relational data sets. Network structure indices (NSIs) are a proven technique for indexing network structure and efficiently finding short paths. We show how incorporating NSIs into these graph clustering algorithms can overcome these complexity limitations. We also present promising quantitative and qualitative evaluations of the modified algorithms on synthetic and real data sets. 1.
Bias%2FVariance Analysis for Relational Domains.

Finding tribes identifying close%2Dknit individuals from employment patterns.
We present a family of algorithms to uncover tribes—groups of individuals who share unusual sequences of affiliations. While much work inferring community structure describes large-scale trends, we instead search for small groups of tightly linked individuals who behave anomalously with respect to those trends. We apply the algorithms to a large temporal and relational data set consisting of millions of employment records from the National Association of Securities Dealers. The resulting tribes contain individuals at higher risk for fraud, are homogenous with respect to risk scores, and are geographically mobile, all at significant levels compared to random or to other sets of individuals who share affiliations.
Relational data pre%2Dprocessing techniques for improved securities fraud detection.
Commercial datasets are often large, relational, and dynamic. They contain many records of people, places, things, events and their interactions over time. Such datasets are rarely structured appropriately for knowledge discovery, and they often contain variables whose meanings change across different subsets of the data. We describe how these challenges were addressed in a collaborative analysis project undertaken by the University of Massachusetts Amherst and the National Association of Securities Dealers (NASD). We describe several methods for data preprocessing that we applied to transform a large, dynamic, and relational dataset describing nearly the entirety of the U.S. securities industry, and we show how these methods made the dataset suitable for learning statistical relational models. To better utilize social structure, we first applied known consolidation and link formation techniques to associate individuals with branch office locations. In addition, we developed an innovative technique to infer professional associations by exploiting dynamic employment histories. Finally, we applied normalization techniques to create a suitable class label that adjusts for spatial, temporal, and other heterogeneity within the data. We show how these pre-processing techniques combine to provide the necessary foundation for learning high-performing statistical models of fraudulent activity.
Recommending citations for academic papers.
Abstract. Substantial effort is wasted in scientific circles by researchers who rediscover ideas that have already been published in the literature. This problem has been alleviated somewhat by the availability of recent academic work online. However, the kinds of text search systems in popular use today are poor at handling vocabulary mismatch, so a researcher must know the words used in relevant documents in order to find them. This makes serendipitous results unlikely. We approach the problem of literature search by considering an unpublished manuscript as a query to a search system. With this approach, the entire text content of the paper can be used in the search process. We use the text of previous literature as well as the citation graph that connects it to find relevant related material. We evaluate our technique with manual and automatic evaluation methods, and find an order of magnitude improvement in mean average precision as compared to a text similarity baseline. 1
Representing documents with named entities for story link detection %28SLD%29.

MaxProp Routing for Vehicle%2DBased Disruption%2DTolerant Networks.
Abstract — Disruption-tolerant networks (DTNs) attempt to route network messages via intermittently connected nodes. Routing in such environments is difficult because peers have little information about the state of the partitioned network and transfer opportunities between peers are of limited duration. In this paper, we propose MaxProp, a protocol for effective routing of DTN messages. MaxProp is based on prioritizing both the schedule of packets transmitted to other peers and the schedule of packets to be dropped. These priorities are based on the path likelihoods to peers according to historical data and also on several complementary mechanisms, including acknowledgments, a head-start for new packets, and lists of previous intermediaries. Our evaluations show that MaxProp performs better than protocols that have access to an oracle that knows the schedule of meetings between peers. Our evaluations are based on 60 days of traces from a real DTN network we have deployed on 30 buses. Our network, called UMassDieselNet, serves a large geographic area between five colleges. We also evaluate MaxProp on simulated topologies and show it performs well in a wide variety of DTN environments. I.
Using structure indices for efficient approximation of network properties.
Statistics on networks have become vital to the study of relational data drawn from areas including bibliometrics, fraud detection, bioinformatics, and the Internet. Calculating many of the most important measures—such as betweenness centrality, closeness centrality, and graph diameter—requires identifying short paths in these networks. However, finding these short paths can be intractable for even moderate-size networks. We introduce the concept of a network structure index (NSI), a composition of (1) a set of annotations on every node in the network and (2) a function that uses the annotations to estimate graph distance between pairs of nodes. We present several varieties of NSIs, examine their time and space complexity, and analyze their performance on synthetic and real data sets. We show that creating an NSI for a given network enables extremely efficient and accurate estimation of a wide variety of network statistics on that network.
Introduction to the special issue on multi%2Drelational data mining and statistical relational learning.

A Relational Representation for Procedural Task Knowledge.
Knowledge representation is a traditional field in artificial intelligence. Researchers have developed various ways to represent and share information among intelligent agents. Agents that share resources, data, information, and knowledge perform better than agents working alone. However, previous research also reveals that sharing knowledge among a large number of entities in an open environment is a problem yet to be solved. Intelligent robots are designed and produced by different manufacturers. They have various physical attributes and employ different knowledge representations. Therefore, any non-standard or non-widely-adopted technology is unsuitable to provide a satisfactory solution to the knowledge sharing problem. In this research, we pose robot knowledge sharing as an activity to be developed in an open environment- the World Wide Web. Just as search engines like Google provide enormous power for information exchange and sharing for humans, we believe a searching mechanism designed for intelligent agents can provide a robust approach for sharing knowledge among robots. We have developed: (1) a knowledge representation for robots that allows Internet access, (2) a knowledge organization and search indexing engine, and (3) a query/reply mechanism between robots and the search engine.
Leveraging Relational Autocorrelation with Latent Group Models.
Abstract. The presence of autocorrelation provides strong motivation for using relational techniques for learning and inference. Autocorrelation is a statistical dependency between the values of the same variable on related entities and is a nearly ubiquitous characteristic of relational data sets. Recent research has explored the use of collective inference techniques to exploit this phenomenon. These techniques achieve significant performance gains by modeling observed correlations among class labels of related instances, but the models fail to capture a frequent cause of autocorrelation—the presence of underlying groups that influence the attributes on a set of entities. We propose a latent group model (LGM) for relational data, which discovers and exploits the hidden structures responsible for the observed autocorrelation among class labels. Modeling the latent group structure improves model performance, increases inference efficiency, and enhances our understanding of the datasets. We evaluate performance on three relational classification tasks and show that LGM outperforms models that ignore latent group structure when there is little known information with which to seed inference.
Decentralized Search in Networks Using Homophily and Degree Disparity.

Using relational knowledge discovery to prevent securities fraud.
We describe an application of relational knowledge discovery to a key regulatory mission of the National Association of Securities Dealers (NASD). NASD is the world’s largest private-sector securities regulator, with responsibility for preventing and discovering misconduct among securities brokers. Our goal was to help focus NASD’s limited regulatory resources on the brokers who are most likely to engage in securities violations. Using statistical relational learning algorithms, we developed models that rank brokers with respect to the probability that they would commit a serious violation of securities regulations in the near future. Our models incorporate organizational relationships among brokers (e.g., past coworker), which domain experts consider important but have not been easily used before now. The learned models were subjected to an extensive evaluation using more than 18 months of data unseen by the model developers and comprising over two person weeks of effort by NASD staff. Model predictions were found to correlate highly with the subjective evaluations of experienced NASD examiners. Furthermore, in all performance measures, our models performed as well as or better than the handcrafted rules that are currently in use at NASD.
Creating social networks to improve peer%2Dto%2Dpeer networking.

Privacy Vulnerabilities in Encrypted HTTP Streams.
Abstract. Encrypting traffic does not prevent an attacker from performing some types of traffic analysis. We present a straightforward traffic analysis attack against encrypted HTTP streams that is surprisingly effective in identifying the source of the traffic. An attacker starts by creating a profile of the statistical characteristics of web requests from interesting sites, including distributions of packet sizes and inter-arrival times. Later, candidate encrypted streams are compared against these profiles. In our evaluations using real traffic, we find that many web sites are subject to this attack. With a training period of 24 hours and a 1 hour delay afterwards, the attack achieves only 23 % accuracy. However, an attacker can easily pre-determine which of trained sites are easily identifiable. Accordingly, against 25 such sites, the attack achieves 40% accuracy; with three guesses, the attack achieves 100 % accuracy for our data. Longer delays after training decrease accuracy, but not substantially. We also propose some countermeasures and improvements to our current method. Previous work analyzed SSL traffic to a proxy, taking advantage of a known flaw in SSL that reveals the length of each web object. In contrast, we exploit the statistical characteristics of web streams that are encrypted as a single flow, which is the case with WEP/WPA, IPsec, and SSH tunnels. 1
Leveraging relational autocorrelation with latent group models.
Abstract. The presence of autocorrelation provides strong motivation for using relational techniques for learning and inference. Autocorrelation is a statistical dependency between the values of the same variable on related entities and is a nearly ubiquitous characteristic of relational data sets. Recent research has explored the use of collective inference techniques to exploit this phenomenon. These techniques achieve significant performance gains by modeling observed correlations among class labels of related instances, but the models fail to capture a frequent cause of autocorrelation—the presence of underlying groups that influence the attributes on a set of entities. We propose a latent group model (LGM) for relational data, which discovers and exploits the hidden structures responsible for the observed autocorrelation among class labels. Modeling the latent group structure improves model performance, increases inference efficiency, and enhances our understanding of the datasets. We evaluate performance on three relational classification tasks and show that LGM outperforms models that ignore latent group structure when there is little known information with which to seed inference.
The case for anomalous link discovery.
In this paper, we consider the link prediction problem, where we are given a partial snapshot of a network at some time and the goal is to predict additional links at a later time. The accuracy of the current prediction methods is quite low due to the extreme class skew and the large number of potential links. In this paper, we describe learning algorithms based on chance constrained programs and show that they exhibit all the properties needed for a good link predictor, namely, allow preferential bias to positive or negative class; handle skewness in the data; and scale to large networks. Our experimental results on three real-world coauthorship networks show significant improvement in prediction accuracy over baseline algorithms. 1
Fast and efficient voltage scheduling by evolutionary slack distribution.
To minimize energy consumption by voltage scaling in design of heterogeneous real-time embedded systems, it is necessary to perform two distinct tasks: task scheduling (TS) and voltage selection (VS). Techniques proposed to date either are fast but yield inefficient results, or output efficient solutions after many slow iterations. As a core problem to solve in the inner loop of a system-level optimization cycle, it is critical that the algorithm be fast while producing high quality results. This paper presents a new technique called Evolutionary Relative Slack Distribution Voltage Scheduling (ERSD-VS) that achieves both speed and efficiency. It addresses priority adjustment and slack distribution issues with low cost heuristics. Experimental results from running publicly available testbenches show up to 42% energy saving compared to a published technique called EVEN-VS. It also shows up to 70 times speed improvement compared to an efficient technique called EE-GLSA.
Dependency Networks for Relational Data.
Instance independence is a critical assumption of traditional machine learning methods contradicted by many relational datasets. For example, in scientific literature datasets there are dependencies among the references of a paper. Recent work on graphical models for relational data has demonstrated significant performance gains for models that exploit the dependencies among instances. In this paper, we present relational dependency networks (RDNs), a new form of graphical model capable of reasoning with such dependencies in a relational setting. We describe the details of RDN models and outline their strengths, most notably the ability to learn and reason with cyclic relational dependencies. We present RDN models learned on a number of real-world datasets, and evaluate the models in a classification context, showing significant performance improvements. In addition, we use synthetic data to evaluate the quality of model learning and inference procedures. 1.
Why collective inference improves relational classification.
Procedures for collective inference make simultaneous statistical judgments about the same variables for a set of related data instances. For example, collective inference could be used to simultaneously classify a set of hyperlinked documents or infer the legitimacy of a set of related financial transactions. Several recent studies indicate that collective inference can significantly reduce classification error when compared with traditional inference techniques. We investigate the underlying mechanisms for this error reduction by reviewing past work on collective inference and characterizing different types of statistical models used for making inference in relational data. We show important differences among these models, and we characterize the necessary and sufficient conditions for reduced classification error based on experiments with real and simulated data.
Simple Estimators for Relational Bayesian Classifiers.
This paper evaluates several modifications of the  Simple Bayesian Classifier to enable estimation  and inference over relational data. The resulting  Relational Bayesian Classifiers are evaluated on  three real-world datasets and compared to a  baseline SBC using no relational information
Avoiding Bias when Aggregating Relational Data with Degree Disparity.
A common characteristic of relational data sets —degree disparity—can lead relational learning algorithms to discover misleading correlations. Degree disparity occurs when the frequency of a relation is correlated with the values of the target variable. In such cases, aggregation functions used by many relational learning algorithms will result in misleading correlations and added complexity in models. We examine this problem through a combination of simulations and experiments. We show how two novel hypothesis testing procedures can adjust for the effects of using aggregation functions in the presence of degree disparity. 1.
Identifying Predictive Structures in Relational Data Using Multiple Instance Learning.
This paper introduces an approach for identifying  predictive structures in relational data using  the multiple-instance framework. By a predictive  structure, we mean a structure that can explain a  given labeling of the data and can predict labels  of unseen data. Multiple-instance learning has  previously only been applied to flat, or propositional,  data and we present a modification to the  framework that allows multiple-instance techniques  to be used on relational data. We present  experimental results using a relational modification  of the diverse density method (Maron, 1998;  Maron &amp; Lozano-P erez, 1998) and of a method  based on the chi-squared statistic (McGovern &amp;  Jensen, 2003). We demonstrate that multipleinstance  learning can be used to identify predictive  structures on both a small illustrative data set  and the Internet Movie Database. We compare  the classification results to a k-nearest neighbor  approach.
Information awareness a prospective technical assessment.
Recent proposals to apply data mining systems to problems in law enforcement, national security, and fraud detection have attracted both media attention and technical critiques of their expected accuracy and impact on privacy. Unfortunately, the majority of technical critiques have been based on simplistic assumptions about data, classifiers, inference procedures, and the overall architecture of such systems. We consider these critiques in detail, and we construct a simulation model that more closely matches realistic systems. We show how both the accuracy and privacy impact of a hypothetical system could be substantially improved, and we discuss the necessary and sufficient conditions for this improvement to be achieved. This analysis is neither a defense nor a critique of any particular system concept. Rather, our model suggests alternative technical designs that could mitigate some concerns, but also raises more specific conditions that must be met for such systems to be both accurate and socially desirable.
Information awareness a prospective technical assessment.
Recent proposals to apply data mining systems to problems in law enforcement, national security, and fraud detection have attracted both media attention and technical critiques of their expected accuracy and impact on privacy. Unfortunately, the majority of technical critiques have been based on simplistic assumptions about data, classifiers, inference procedures, and the overall architecture of such systems. We consider these critiques in detail, and we construct a simulation model that more closely matches realistic systems. We show how both the accuracy and privacy impact of a hypothetical system could be substantially improved, and we discuss the necessary and sufficient conditions for this improvement to be achieved. This analysis is neither a defense nor a critique of any particular system concept. Rather, our model suggests alternative technical designs that could mitigate some concerns, but also raises more specific conditions that must be met for such systems to be both accurate and socially desirable.


Exploiting relational structure to understand publication patterns in high%2Denergy physics.
We analyze publication patterns in theoretical high-energy physics using a relational learning approach. We focus on four related areas: understanding and identifying patterns of citations, examining publication patterns at the author level, predicting whether a paper will be accepted by specific journals, and identifying research communities from the citation patterns and paper text. Each of these analyses contributes to an overall understanding of theoretical highenergy physics. 1.
Linkage and Autocorrelation Cause Feature Selection Bias in Relational Learning.
Two common characteristics of relational data  sets --- concentrated linkage and relational autocorrelation  --- can cause learning algorithms to  be strongly biased toward certain features, irrespecti  e of their predicti e power. We identify  these characteristics, define quantitati e measures  of their se erity, and explain how they produce  this bias. We show how linkage and autocorrelation  affect a representati e algorithm for  feature selection by applying the algorithm to  synthetic data and to data drawn from the Internet  Mo ie Database.
Autocorrelation and Linkage Cause Bias in Evaluation of Relational Learners.
Two common characteristics of relational data sets — concentrated linkage and relational auto-correlation — can cause traditional methods of evaluation to greatly overestimate the accuracy of induced models on test sets. We identify these characteristics, define quantitative measures of their severity, and explain how they produce this bias. We show how linkage and autocorrelation affect estimates of model accuracy by applying FOIL to synthetic data and to data drawn from the Internet Movie Database. We show how a modified sampling procedure can eliminate the bias.
Language Models for Financial News Recommendation.
	 9 9999 9999 9999 9999 9999 9999 9999 9999 9999   ,&amp;-.	 /102	43!&amp;,&#034;65.	798: 	;=&lt;2	 &amp;5&gt; 	7&amp;7#$?@(A	 /102	43!&amp;,&#034;65.	798: 	;=&lt;2	 &amp;5&gt; 7#$+J?2*+$+	8KLJ/ 	C8F8F	B&amp; 	+&amp;&#039;F ()L+&amp;	 M +&amp;	.,417&amp;: 7&amp;$DN4OP	 B8:F02	.J3!&amp;J;QH&gt; 7#$+R2 G S0!$T	 7&amp;$DN4OP	 B8:F02	.J3!&amp;J;QH&gt; 28990-45710   C	A&#034;V ()R+ R()&amp; 28800-44660  F02	.J3!&amp;J;QH&gt; 28990  899-43620  F  ()R+ R()&amp; 28800-44660  F02	.J3!&amp;J;QH&gt; 28990-457 [R 0  F  ()R+ R()&amp; 28800-44660  F02	.J3!&amp;J;QH&gt; 28990 - * 6C84J*0&amp;&amp;&#039;\	JC; 29100-41530  QH&gt; 289 ]&amp;&#039;7#$Z *0&amp;&amp;&#039;\	JC; 29100-41530  QH&gt; 28990-457 H,.7#$+R	* *	#&#034;X$*.T 	C8F8F	U ()A+ W.4 46&amp;&#039;C7&amp;$&amp;.&amp;J4&amp;3[&#034;_&#034;`\ 8F8F	U ()A+ W.4 2894  8a&amp;b 8FU&#034;I&amp;0&amp;7&amp;#c$N]		C8F8F .E,+&amp;	*.4 ()&amp;7&amp;7\4OP	 ,02	.J3!&amp;B&#034;I/+G:8: J;bE1	8FC&gt; + &amp;7\4OP	 ,02	.J3!&amp;B&#034;I/+G:8: J;bE1	8FC&gt; T5G07&amp;$BJ&amp; )&#034;` &amp;$+I	C7%102d  J;bE1	8FC&gt; 29000 -  Keywords  e 7&amp;J4&amp;Cf?!	 C8F8F	 A+$+ 8/? g!S8F&amp;&amp;&#039;?&amp;8F9 000-35250 &amp;		 ()&amp; Cf?!	 C8F8F	 A+$+ 8/? g!S8F&amp;&amp;&#039;?&amp;8F9 000-35250 
Knowledge Discovery from Graphs %28Invited Talk%29.

Reports on the AAAI Fall Symposia %28November 1999 and November 1998%29.

Data Snooping
This paper is a scientific introduction to technical stock analysis. The problems with performance evaluation of near-random-walk processes are illustrated with some examples and the consequences for algorithm development and performance evaluation are discussed. The prediction task is formalized. Existing benchmarks...
Learning Quantitative Knowledge for Multiagent Coordination.
A central challenge of multiagent coordination is reasoning about how the actions of one agent affect the actions of another. Knowledge of these interrelationships can help coordinate agents --- preventing conflicts and exploiting beneficial relationships among actions. We explore three interlocking methods that learn quantitative knowledge of such non-local effects in TAEMS, a well-developed framework for multiagent coordination. The surprising simplicity and effectiveness of these methods demonstrates how agents can learn domain-specific knowledge quickly, extending the utility of coordination frameworks that explicitly represent coordination knowledge.  Content Areas: Intelligent Agents: Tasks or Problems: Multi-agent communication, coordination, or collaboration; Intelligent Agents: Tasks or Problems: Learning and adaptation; Machine Learning and Discovery: Techniques or Algorithms: Specialized learning algorithms  Introduction  A major challenge of designing effective multiagent s...
Toward a Theoretical Understanding of Why and When Decision Tree Pruning Algorithms Fail.
Recent empirical studies revealed two surprising  pathologies of several common decision tree pruning  algorithms. First, tree size is often a linear function  of training set size, even when additional tree structure  yields no increase in accuracy. Second, building  trees with data in which the class label and the attributes  are independent often results in large trees.
Efficient Progressive Sampling.
Having access to massive amounts of data does not necessarily imply that induction algorithms must use them all.  Samples often provide the same accuracy with far less computational cost. However, the correct sample size rarely is obvious. We analyze methods for progressive sampling---  using progressively larger samples as long as model accuracy improves. We explore several notions of efficient progressive sampling. We analyze efficiency relative to induction with all instances; we show that a simple, geometric sampling schedule is asymptotically optimal, and we describe how best to take into account prior expectations of accuracy convergence. We then describe the issues involved in instantiating an efficient progressive sampler, including how to detect convergence. Finally, we provide empirical results comparing a variety of progressive sampling methods. We conclude that progressive sampling can be remarkably efficient.   1 Introduction  Induction algorithms face competing requiremen...
Coordinating agent activities in knowledge discovery processes.
Knowledge discovery in databases (KDD) is an increasingly widespread activity. KDD processes may entail the use of a large number of data manipulation and analysis techniques, and new techniques are being developed on an ongoing basis. A challenge for the effective use of KDD is coordinating the use of these techniques, which may be highly specialized, conditional and contingent. Additionally, the understanding and validity of KDD results can depend critically on the processes by which they were derived. We propose to use process programming to address the coordination of agents in the use of KDD techniques. We illustrate this approach using the process language Little-JIL to program a representative bivariate regression process. With Little-JIL programs we can clearly capture the coordination of KDD activities, including control flow, pre- and post-requisites, exception handling, and resource usage.
Large Datasets Lead to Overly Complex Models An Explanation and a Solution.
This paper explores unexpected results that lie at  the intersection of two common themes in the KDD  community: large datasets and the goal of building  compact models. Experiments with many different  datasets and several model construction algorithms  (including tree learning algorithms suchasc4.5 with  three different pruning methods, and rule learning algorithms  such as c4.5rules and ripper) show that  increasing the amount of data used to build a model often  results in a linear increase in model size, even when  that additional complexity results in no significantincrease  in model accuracy. Despite the promise of better  parameter estimation held out by large datasets, as a  practical matter, models built with large amounts of  data are often needlessly complex and cumbersome. In  the case of decision trees, the cause of this pathology is  identified as a bias inherentinseveral common pruning  techniques. Pruning errors made low in the tree, where  there is insufficient data to make accurate parameter  estimates, are propagated and magnified higher in the  tree, working against the accurate parameter estimates  that are made possible there by abundant data. We  propose a general solution to this problem based on a  statistical technique known as randomization testing,  and empirically evaluate its utility.
Plant location with minimum inventory.

The Effects of Training Set Size on Decision Tree Complexity.
This paper presents experiments with 19 datasets and 5 decision tree  pruning algorithms that show that increasing training set size often  results in a linear increase in tree size, even when that additional  complexity results in no significant increase in classification accuracy.
Building Simple Models A Case Study with Decision Trees.

Adjusting for Multiple Comparisons in Decision Tree Pruning.

